package com.leetcode.LC_MED;

import java.util.Arrays;

public class LC31 {
    public void nextPermutation(int[] nums) {
        //5423
        if (nums.length == 1) {
            return;
        }
        boolean f = false;
        int a = nums.length - 1, i, j;
        for (i = a; i >= 0; i--) {
            for (j = i; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                    f = true;
                    break;
                }
            }
            if (f) {
                Arrays.sort(nums, j + 1, nums.length);
                break;
            }
        }
        if (!f) {
            Arrays.sort(nums);
        }
        for (int num : nums) {
            System.out.print(num);
        }
    }

    public void nextPermutation2(int[] nums) {
        /*
        算法思路：
        从后往前找出第一个后大于前的位置i与i-1
        对于i之后的元素排序[i，len)左闭右开
        排序后找到[i，len)第一个大于i-1位置元素的位置进行交换
        返回结果
        如果不存在这种情况，则直接对原数组进行排序
         */
        if (nums.length == 1) {
            return;
        }
        int a = nums.length - 1, i, j;
        for (i = a; i >= 0; i--) {
            if (i - 1 >= 0 && nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, nums.length);
                for (j = i; j < nums.length; j++) {
                    if (nums[j] > nums[i - 1]) {
                        int tmp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = tmp;
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
    }

    public static void main(String[] args) {//132->213//123->132
        new LC31().nextPermutation2(new int[]{3, 2, 1});
    }
}
